package com.datastructures2.search;

import com.datastructures2.背包队列栈.Queue;

/**
 * 顺序查找（基于无序链表）
 * 未命中和命中都需要N次比较
 * 命中最坏需要N次比较
 * @author MaoLin Wang
 * @date 2020/3/118:01
 */
public class SequentialSearchST<Key, Value> {
    /**
     * 首节点
     */
    private Node first;
    private int size;


    private class Node {
        private Key key;
        private Value value;
        private Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 根据key查询对应的值，一个个往下遍历直到找到相等的key，返回对应的值，否则返回null
     * @param key
     * @return
     */
    public Value get(Key key) {
        for (Node x = first; x != null; x = x.next) {

            if (key.equals(x.key)) {
                return x.value;
            }
        }
        return null;
    }

    /**
     * 加入一个元素
     * @param key
     * @param value
     */
    public void put(Key key, Value value) {
        for (Node x = first; x != null; x = x.next) {
            //key已存在，更新对应的值
            if (key.equals(x.key)) {
                x.value = value;
                return;
            }
        }
        //key不存在，新添加一个节点
        first = new Node(key, value, first);
        size++;
    }
    public boolean isEmpty() {
        return size == 0;
    }

    private int size() {
        return size;
    }
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }

    /**
     * 删除key对应的节点
     * @param key
     */
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        first = delete(first, key);
    }

    /**
     * 递归查找，直到找到相等的key，正常删除链表节点
     * @param x
     * @param key
     * @return
     */
    private Node delete(Node x, Key key) {
        if (x == null) return null;
        if (key.equals(x.key)) {
            size--;
            return x.next;
        }
        x.next = delete(x.next, key);
        return x;
    }
    public Iterable<Key> keys()  {
        Queue<Key> queue=new Queue<>();
        while (first!=null){
            queue.enqueue(first.key);
            first=first.next;
        }
        return queue;
    }
}
